package com.datastructure.test.insertionsortlist;

public class InsertionSortListNode {

    public static void main(String[] args) {
        InsertionSortListNode insertionSortListNode = new InsertionSortListNode();
        ListNode head=new ListNode(2);
        head.next=new ListNode(1);
        ListNode listNode = insertionSortListNode.insertionSortList(head);
        System.out.println(listNode);
    }

    public ListNode insertionSortList (ListNode head) {
        // write code here
        if(head==null||head.next==null){
            return head;
        }
        ListNode cur = new ListNode(head.val);
        ListNode temp = head.next;
        while (temp!=null){
            cur = insertListNode(cur,new ListNode(temp.val));
            temp=temp.next;
        }
        return cur;
    }

    private ListNode insertListNode(ListNode cur, ListNode temp) {
        if(cur==null){
            return cur;
        }
        ListNode lastListNode = null;
        int tempValue = temp.val;
        ListNode res = cur;
        while (cur!=null){
            if(tempValue<= cur.val){
                if(lastListNode==null){
                    temp.next=cur;
                    return temp;
                } else {
                    lastListNode.next=temp;
                    temp.next=cur;
                    return res;
                }
            }
            lastListNode=cur;
            cur=cur.next;
        }
        lastListNode.next=temp;
        return res;
    }

    public ListNode insertionSortList1 (ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode dum = new ListNode(-1);
        dum.next = head;
        ListNode lastedSorted = head;
        ListNode cur = head.next;
        while(cur != null){
            if(lastedSorted.val <= cur.val)
                lastedSorted = lastedSorted.next;
            else{
                ListNode prev = dum;
                while(prev.next.val <= cur.val)
                    prev = prev.next;
                lastedSorted.next = cur.next;
                cur.next = prev.next;
                prev.next = cur;
            }
            cur = lastedSorted.next;
        }
        return dum.next;
    }
}
class ListNode {
   int val;
   ListNode next = null;
   public ListNode(int val) {
     this.val = val;
   }
 }